

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>toydata package &mdash; ToyData 1.0 documentation</title>
  

  
  
  
  

  
  <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
        <script type="text/javascript" src="_static/jquery.js"></script>
        <script type="text/javascript" src="_static/underscore.js"></script>
        <script type="text/javascript" src="_static/doctools.js"></script>
        <script type="text/javascript" src="_static/language_data.js"></script>
    
    <script type="text/javascript" src="_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <link rel="index" title="Index" href="genindex.html" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="prev" title="toydata" href="modules.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="index.html" class="icon icon-home"> ToyData
          

          
          </a>

          
            
            
              <div class="version">
                1.0
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption"><span class="caption-text">Contents:</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="Intro.html">Introductions</a></li>
<li class="toctree-l1"><a class="reference internal" href="Overview.html">Overview</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="modules.html">toydata</a><ul class="current">
<li class="toctree-l2 current"><a class="current reference internal" href="#">toydata package</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#submodules">Submodules</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.Graph">toydata.Graph module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.LinkedLists">toydata.LinkedLists module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.Maps">toydata.Maps module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.PositionalList">toydata.PositionalList module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.PriorityQueue">toydata.PriorityQueue module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.Queue">toydata.Queue module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.SearchTree">toydata.SearchTree module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.Stack">toydata.Stack module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.Tree">toydata.Tree module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata.utils">toydata.utils module</a></li>
<li class="toctree-l3"><a class="reference internal" href="#module-toydata">Module contents</a></li>
</ul>
</li>
</ul>
</li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="index.html">ToyData</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="index.html">Docs</a> &raquo;</li>
        
          <li><a href="modules.html">toydata</a> &raquo;</li>
        
      <li>toydata package</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="_sources/toydata.rst.txt" rel="nofollow"> View page source</a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="toydata-package">
<h1>toydata package<a class="headerlink" href="#toydata-package" title="Permalink to this headline">¶</a></h1>
<div class="section" id="submodules">
<h2>Submodules<a class="headerlink" href="#submodules" title="Permalink to this headline">¶</a></h2>
</div>
<div class="section" id="module-toydata.Graph">
<span id="toydata-graph-module"></span><h2>toydata.Graph module<a class="headerlink" href="#module-toydata.Graph" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.Graph.Graph">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Graph.</code><code class="sig-name descname">Graph</code><span class="sig-paren">(</span><em class="sig-param">directed=False</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Representation of a simple graph using an adjacency map.
Adjacency Map Structure implemented with hash tables.</p>
<dl class="class">
<dt id="toydata.Graph.Graph.Edge">
<em class="property">class </em><code class="sig-name descname">Edge</code><span class="sig-paren">(</span><em class="sig-param">u</em>, <em class="sig-param">v</em>, <em class="sig-param">x</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Edge"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Edge" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>lightweight edge structure for a graph</p>
<dl class="method">
<dt id="toydata.Graph.Graph.Edge.element">
<code class="sig-name descname">element</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Edge.element"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Edge.element" title="Permalink to this definition">¶</a></dt>
<dd><p>Return element associated with this edge</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.Edge.endpoint">
<code class="sig-name descname">endpoint</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Edge.endpoint"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Edge.endpoint" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (u, v) tuple for vertices u and v</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.Edge.opposite">
<code class="sig-name descname">opposite</code><span class="sig-paren">(</span><em class="sig-param">v</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Edge.opposite"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Edge.opposite" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the vertex that is opposite v on the edge</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Graph.Graph.Vertex">
<em class="property">class </em><code class="sig-name descname">Vertex</code><span class="sig-paren">(</span><em class="sig-param">x</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Vertex"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Vertex" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Lightweight vertex structure for a graph</p>
<dl class="attribute">
<dt id="toydata.Graph.Graph.Vertex.e">
<code class="sig-name descname">e</code><a class="headerlink" href="#toydata.Graph.Graph.Vertex.e" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.Vertex.element">
<code class="sig-name descname">element</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.Vertex.element"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.Vertex.element" title="Permalink to this definition">¶</a></dt>
<dd><p>Return element associated with this vertex.</p>
</dd></dl>

<dl class="attribute">
<dt id="toydata.Graph.Graph.Vertex.l">
<code class="sig-name descname">l</code><a class="headerlink" href="#toydata.Graph.Graph.Vertex.l" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="attribute">
<dt id="toydata.Graph.Graph.Vertex.m">
<code class="sig-name descname">m</code><a class="headerlink" href="#toydata.Graph.Graph.Vertex.m" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="attribute">
<dt id="toydata.Graph.Graph.Vertex.n">
<code class="sig-name descname">n</code><a class="headerlink" href="#toydata.Graph.Graph.Vertex.n" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="attribute">
<dt id="toydata.Graph.Graph.Vertex.t">
<code class="sig-name descname">t</code><a class="headerlink" href="#toydata.Graph.Graph.Vertex.t" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.bfs">
<code class="sig-name descname">bfs</code><span class="sig-paren">(</span><em class="sig-param">s</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.bfs"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.bfs" title="Permalink to this definition">¶</a></dt>
<dd><p>Perform BFS of the undiscovered portion of Graph g starting at
Vertex s.</p>
<p>discovered is a dictionary mapping each vertex to the edge that 
was used to discover it during the BFS(s should be mapped to None
prior to the call). Newly discovered vertices will be added to the
dictionary as a result.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.construct_path">
<code class="sig-name descname">construct_path</code><span class="sig-paren">(</span><em class="sig-param">u</em>, <em class="sig-param">v</em>, <em class="sig-param">dfs=True</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.construct_path"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.construct_path" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.degree">
<code class="sig-name descname">degree</code><span class="sig-paren">(</span><em class="sig-param">v</em>, <em class="sig-param">outgoing=True</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.degree"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.degree" title="Permalink to this definition">¶</a></dt>
<dd><p>Return number of (outgoing) edges incident to vertex v
in the graph. If graph is directed, optional parameter 
used to count incoming edges</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.dfs">
<code class="sig-name descname">dfs</code><span class="sig-paren">(</span><em class="sig-param">u</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.dfs"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.dfs" title="Permalink to this definition">¶</a></dt>
<dd><p>Perform DFS of the undiscovered portion of Graph g
starting at Vertex u.</p>
<p>Discovered is a dictionary mapping each vertex to the
edge that was used to discover it during the DFS(u should
be “discovered” prior to the call.)Newly discovered vertices
will be added to the dictionary as a result.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.dfs_complete">
<code class="sig-name descname">dfs_complete</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.dfs_complete"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.dfs_complete" title="Permalink to this definition">¶</a></dt>
<dd><p>Perform DFS for entire graph and return forest as a dictionary.</p>
<p>Result maps each vertex v tp the edge that was used to discover it.
(Vertices that are roots of a DFS tree are mapped to None)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.edge_count">
<code class="sig-name descname">edge_count</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.edge_count"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.edge_count" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the number of edges in the graph</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.edges">
<code class="sig-name descname">edges</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.edges"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.edges" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a set of all edges of the graph</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.floyd_warshall">
<code class="sig-name descname">floyd_warshall</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.floyd_warshall"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.floyd_warshall" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a new graph that is the transitive closure of g</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.get_edge">
<code class="sig-name descname">get_edge</code><span class="sig-paren">(</span><em class="sig-param">u</em>, <em class="sig-param">v</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.get_edge"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.get_edge" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the edge from u to v, or None if not adjacent</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.incident_edges">
<code class="sig-name descname">incident_edges</code><span class="sig-paren">(</span><em class="sig-param">v</em>, <em class="sig-param">outgoing=True</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.incident_edges"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.incident_edges" title="Permalink to this definition">¶</a></dt>
<dd><p>Return all(outgoing) edges incident to vertex v in
the graph. If graph is directed, optional parameter used
to request incoming edges</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.insert_edge">
<code class="sig-name descname">insert_edge</code><span class="sig-paren">(</span><em class="sig-param">u</em>, <em class="sig-param">v</em>, <em class="sig-param">x=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.insert_edge"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.insert_edge" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert and return a new Edge from u to v with auxliary element x</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.insert_vertex">
<code class="sig-name descname">insert_vertex</code><span class="sig-paren">(</span><em class="sig-param">x=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.insert_vertex"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.insert_vertex" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert and return a new Vertex with element x</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.is_directed">
<code class="sig-name descname">is_directed</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.is_directed"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.is_directed" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if this is a directed graph; False if undirected.
Property is based on the original declaration of the graph,
not its content</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.remove_edges">
<code class="sig-name descname">remove_edges</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.remove_edges"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.remove_edges" title="Permalink to this definition">¶</a></dt>
<dd><p>Delete adn return edge e from graph</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.remove_vertex">
<code class="sig-name descname">remove_vertex</code><span class="sig-paren">(</span><em class="sig-param">v</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.remove_vertex"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.remove_vertex" title="Permalink to this definition">¶</a></dt>
<dd><p>InserDeltet and return the Vertex v
Raise KeyError is v not in graph.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.vertex_count">
<code class="sig-name descname">vertex_count</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.vertex_count"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.vertex_count" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the number of vertives in the graph</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Graph.Graph.vertices">
<code class="sig-name descname">vertices</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Graph.html#Graph.vertices"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Graph.Graph.vertices" title="Permalink to this definition">¶</a></dt>
<dd><p>Return an iteration of all vertices of the graph</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.LinkedLists">
<span id="toydata-linkedlists-module"></span><h2>toydata.LinkedLists module<a class="headerlink" href="#module-toydata.LinkedLists" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.LinkedLists.Doublellist">
<em class="property">class </em><code class="sig-prename descclassname">toydata.LinkedLists.</code><code class="sig-name descname">Doublellist</code><span class="sig-paren">(</span><em class="sig-param">items=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Double linked list(with sentinels)</p>
<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.add_first">
<code class="sig-name descname">add_first</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.add_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.add_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Add a node at the first of the list.</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.add_last">
<code class="sig-name descname">add_last</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.add_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.add_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Add a node at the last of the list</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.change">
<code class="sig-name descname">change</code><span class="sig-paren">(</span><em class="sig-param">old_val</em>, <em class="sig-param">new_val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.change"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.change" title="Permalink to this definition">¶</a></dt>
<dd><p>Only change the first node with <cite>old_val</cite> to <cite>new_val</cite></p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.change_all">
<code class="sig-name descname">change_all</code><span class="sig-paren">(</span><em class="sig-param">old_val</em>, <em class="sig-param">new_val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.change_all"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.change_all" title="Permalink to this definition">¶</a></dt>
<dd><p>Change all the node with <cite>old_val</cite> to <cite>new_val</cite></p>
<p>Note: here we use an efficient way to do that</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the first value in the list.
Or raise Empty error if the list is empty.</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.insert_after">
<code class="sig-name descname">insert_after</code><span class="sig-paren">(</span><em class="sig-param">pos_val</em>, <em class="sig-param">ins_val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.insert_after"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.insert_after" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert <cite>ins_val</cite> after <cite>pos_val</cite></p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>If the list is empty or not</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.last">
<code class="sig-name descname">last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.last" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the last value in the list.
Or raise Empty error if the list is empty.</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.remove">
<code class="sig-name descname">remove</code><span class="sig-paren">(</span><em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.remove"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.remove" title="Permalink to this definition">¶</a></dt>
<dd><p>Only remove the first node with value equals <cite>val</cite></p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.remove_all">
<code class="sig-name descname">remove_all</code><span class="sig-paren">(</span><em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.remove_all"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.remove_all" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove all the nodes with value equals <cite>val</cite></p>
<p>Note: here we use an efficient way to do that</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.remove_first">
<code class="sig-name descname">remove_first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.remove_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.remove_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the first node of the list.
Or raise an Empty error if the list is empty.</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.remove_last">
<code class="sig-name descname">remove_last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.remove_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.remove_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the last node of the list</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Doublellist.search">
<code class="sig-name descname">search</code><span class="sig-paren">(</span><em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Doublellist.search"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Doublellist.search" title="Permalink to this definition">¶</a></dt>
<dd><p>If val in list of not</p>
<p>Time complexity: O(n)</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.LinkedLists.Node">
<em class="property">class </em><code class="sig-prename descclassname">toydata.LinkedLists.</code><code class="sig-name descname">Node</code><span class="sig-paren">(</span><em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Node"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Node" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Node in Single linked list.</p>
</dd></dl>

<dl class="class">
<dt id="toydata.LinkedLists.Singlellist">
<em class="property">class </em><code class="sig-prename descclassname">toydata.LinkedLists.</code><code class="sig-name descname">Singlellist</code><span class="sig-paren">(</span><em class="sig-param">items=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>The implementation of single linked list.</p>
<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.add_first">
<code class="sig-name descname">add_first</code><span class="sig-paren">(</span><em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.add_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.add_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Inserting an element at the head of a single linked list</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.add_last">
<code class="sig-name descname">add_last</code><span class="sig-paren">(</span><em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.add_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.add_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Adding element at the end of single linked list</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.change">
<code class="sig-name descname">change</code><span class="sig-paren">(</span><em class="sig-param">old_val</em>, <em class="sig-param">new_val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.change"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.change" title="Permalink to this definition">¶</a></dt>
<dd><p>Change the first node with value “old_val” to “new_val”</p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.change_all">
<code class="sig-name descname">change_all</code><span class="sig-paren">(</span><em class="sig-param">old_val</em>, <em class="sig-param">new_val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.change_all"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.change_all" title="Permalink to this definition">¶</a></dt>
<dd><p>Change all the node with “old_val” to “new_val”</p>
<p>Note that we can do it in O(n), but we used an efficient
algorithm here.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.insert_after">
<code class="sig-name descname">insert_after</code><span class="sig-paren">(</span><em class="sig-param">pos_value</em>, <em class="sig-param">insert_value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.insert_after"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.insert_after" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert the insert_value after the (first)pos_value</p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>If the list is empty or not</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.remove">
<code class="sig-name descname">remove</code><span class="sig-paren">(</span><em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.remove"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.remove" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the first node with value equals to val.</p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.remove_all">
<code class="sig-name descname">remove_all</code><span class="sig-paren">(</span><em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.remove_all"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.remove_all" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove all the node woth value = val</p>
<p>Note that we can do it in O(n), but we used an efficient
algorithm here.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.remove_first">
<code class="sig-name descname">remove_first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.remove_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.remove_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the first element in the single linked list.
Or raise an empty error when there is no node in the list.</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.remove_last">
<code class="sig-name descname">remove_last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.remove_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.remove_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the last element in the single linked list.
Or raise an empty error when there is no node in the list.</p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.LinkedLists.Singlellist.search">
<code class="sig-name descname">search</code><span class="sig-paren">(</span><em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/LinkedLists.html#Singlellist.search"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.LinkedLists.Singlellist.search" title="Permalink to this definition">¶</a></dt>
<dd><p>If value in list or not.</p>
<p>Time complexity: O(n)</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.Maps">
<span id="toydata-maps-module"></span><h2>toydata.Maps module<a class="headerlink" href="#module-toydata.Maps" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.Maps.ChainHashMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">ChainHashMap</code><span class="sig-paren">(</span><em class="sig-param">cap=4</em>, <em class="sig-param">p=10945121</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#ChainHashMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.ChainHashMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Maps.HashMapBase" title="toydata.Maps.HashMapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.HashMapBase</span></code></a></p>
<p>Hash map implemented with seperate chaining for collision resolution</p>
</dd></dl>

<dl class="class">
<dt id="toydata.Maps.HashMapBase">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">HashMapBase</code><span class="sig-paren">(</span><em class="sig-param">cap=4</em>, <em class="sig-param">p=10945121</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#HashMapBase"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.HashMapBase" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Maps.MapBase" title="toydata.Maps.MapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.MapBase</span></code></a></p>
<p>Abstract base class for map using hash-table with MAD compression.</p>
</dd></dl>

<dl class="class">
<dt id="toydata.Maps.MapBase">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">MapBase</code><a class="reference internal" href="_modules/toydata/Maps.html#MapBase"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.MapBase" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">collections.abc.MutableMapping</span></code></p>
<p>Our own abstract base class that incudes a nonpublic _Item class.</p>
</dd></dl>

<dl class="class">
<dt id="toydata.Maps.ProbeHashMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">ProbeHashMap</code><span class="sig-paren">(</span><em class="sig-param">cap=4</em>, <em class="sig-param">p=10945121</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#ProbeHashMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.ProbeHashMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Maps.HashMapBase" title="toydata.Maps.HashMapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.HashMapBase</span></code></a></p>
<p>Hash map implementated with linear probing for collision resolution.</p>
</dd></dl>

<dl class="class">
<dt id="toydata.Maps.SortedTableMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">SortedTableMap</code><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Maps.MapBase" title="toydata.Maps.MapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.MapBase</span></code></a></p>
<p>Map implementation using a sorted table</p>
<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_ge">
<code class="sig-name descname">find_ge</code><span class="sig-paren">(</span><em class="sig-param">k</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_ge"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_ge" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with least key greater that or
equal to k</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_gt">
<code class="sig-name descname">find_gt</code><span class="sig-paren">(</span><em class="sig-param">k</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_gt"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_gt" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with least key strictly greater than k</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_lt">
<code class="sig-name descname">find_lt</code><span class="sig-paren">(</span><em class="sig-param">k</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_lt"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_lt" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with greatest key strictly less than k</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_max">
<code class="sig-name descname">find_max</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_max"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_max" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with maximum key(or None if empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_min">
<code class="sig-name descname">find_min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_min" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with minimum key(or None if empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Maps.SortedTableMap.find_range">
<code class="sig-name descname">find_range</code><span class="sig-paren">(</span><em class="sig-param">start</em>, <em class="sig-param">stop</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Maps.html#SortedTableMap.find_range"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.SortedTableMap.find_range" title="Permalink to this definition">¶</a></dt>
<dd><p>Iterate all (key, value) pairs such that start &lt;= key &lt; stop.
If start is None, iteration begins with minimum key of map.
If stop is None, iteration continues through the maximum key of map.</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Maps.UnsortedTableMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Maps.</code><code class="sig-name descname">UnsortedTableMap</code><a class="reference internal" href="_modules/toydata/Maps.html#UnsortedTableMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Maps.UnsortedTableMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Maps.MapBase" title="toydata.Maps.MapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.MapBase</span></code></a></p>
<p>Map implementation using an unsorted list.</p>
</dd></dl>

</div>
<div class="section" id="module-toydata.PositionalList">
<span id="toydata-positionallist-module"></span><h2>toydata.PositionalList module<a class="headerlink" href="#module-toydata.PositionalList" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.PositionalList.PositionalList">
<em class="property">class </em><code class="sig-prename descclassname">toydata.PositionalList.</code><code class="sig-name descname">PositionalList</code><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.PositionalList._DoublyLinkedBase</span></code></p>
<p>A sequential container of elements allowing positional access</p>
<dl class="class">
<dt id="toydata.PositionalList.PositionalList.Position">
<em class="property">class </em><code class="sig-name descname">Position</code><span class="sig-paren">(</span><em class="sig-param">container</em>, <em class="sig-param">node</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.Position"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.Position" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>A abstraction representing the location of a single element</p>
<dl class="method">
<dt id="toydata.PositionalList.PositionalList.Position.element">
<code class="sig-name descname">element</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.Position.element"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.Position.element" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the element store at this Position</p>
</dd></dl>

</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.add_after">
<code class="sig-name descname">add_after</code><span class="sig-paren">(</span><em class="sig-param">p</em>, <em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.add_after"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.add_after" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert element e into list after Position p and return new Pos</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.add_before">
<code class="sig-name descname">add_before</code><span class="sig-paren">(</span><em class="sig-param">p</em>, <em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.add_before"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.add_before" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert element e into list before Position p and return new Pos</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.add_first">
<code class="sig-name descname">add_first</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.add_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.add_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert element e at the front of the list and return new Pos</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.add_last">
<code class="sig-name descname">add_last</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.add_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.add_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Insert element e at the back of the list and return new Pos</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.after">
<code class="sig-name descname">after</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.after"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.after" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position just after Position p
(or None if p is last)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.before">
<code class="sig-name descname">before</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.before"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.before" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position just before Position p
(or None if p is first)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.delete">
<code class="sig-name descname">delete</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.delete"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.delete" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the element at Position p</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the first Position in the list(or None if list is empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.last">
<code class="sig-name descname">last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.last" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the last Position in the list(or None if list is empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PositionalList.PositionalList.replace">
<code class="sig-name descname">replace</code><span class="sig-paren">(</span><em class="sig-param">p</em>, <em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PositionalList.html#PositionalList.replace"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PositionalList.PositionalList.replace" title="Permalink to this definition">¶</a></dt>
<dd><p>Replace the element at Position p with e.
Return the element formerly at Position p</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.PriorityQueue">
<span id="toydata-priorityqueue-module"></span><h2>toydata.PriorityQueue module<a class="headerlink" href="#module-toydata.PriorityQueue" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.PriorityQueue.HeapPriorityQueue">
<em class="property">class </em><code class="sig-prename descclassname">toydata.PriorityQueue.</code><code class="sig-name descname">HeapPriorityQueue</code><a class="reference internal" href="_modules/toydata/PriorityQueue.html#HeapPriorityQueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.HeapPriorityQueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.PriorityQueue.PriorityQueueBase" title="toydata.PriorityQueue.PriorityQueueBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.PriorityQueue.PriorityQueueBase</span></code></a></p>
<p>A min-oriented priority queue implemented with a binary heap</p>
<dl class="method">
<dt id="toydata.PriorityQueue.HeapPriorityQueue.add">
<code class="sig-name descname">add</code><span class="sig-paren">(</span><em class="sig-param">key</em>, <em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#HeapPriorityQueue.add"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.HeapPriorityQueue.add" title="Permalink to this definition">¶</a></dt>
<dd><p>Add a key-value pair to the priority list</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.HeapPriorityQueue.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#HeapPriorityQueue.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.HeapPriorityQueue.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if priority list is empty</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.HeapPriorityQueue.min">
<code class="sig-name descname">min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#HeapPriorityQueue.min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.HeapPriorityQueue.min" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.HeapPriorityQueue.remove_min">
<code class="sig-name descname">remove_min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#HeapPriorityQueue.remove_min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.HeapPriorityQueue.remove_min" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return (k ,v) tuple with minimum key.
Raise Empty exception if empty</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.PriorityQueue.PriorityQueueBase">
<em class="property">class </em><code class="sig-prename descclassname">toydata.PriorityQueue.</code><code class="sig-name descname">PriorityQueueBase</code><a class="reference internal" href="_modules/toydata/PriorityQueue.html#PriorityQueueBase"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.PriorityQueueBase" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Abstract base class for a priority queue</p>
</dd></dl>

<dl class="class">
<dt id="toydata.PriorityQueue.SortedPriorityQueue">
<em class="property">class </em><code class="sig-prename descclassname">toydata.PriorityQueue.</code><code class="sig-name descname">SortedPriorityQueue</code><a class="reference internal" href="_modules/toydata/PriorityQueue.html#SortedPriorityQueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.SortedPriorityQueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.PriorityQueue.PriorityQueueBase" title="toydata.PriorityQueue.PriorityQueueBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.PriorityQueue.PriorityQueueBase</span></code></a></p>
<p>A min-oriented priority queue implemented with a sorted list</p>
<dl class="method">
<dt id="toydata.PriorityQueue.SortedPriorityQueue.add">
<code class="sig-name descname">add</code><span class="sig-paren">(</span><em class="sig-param">key</em>, <em class="sig-param">value</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#SortedPriorityQueue.add"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.SortedPriorityQueue.add" title="Permalink to this definition">¶</a></dt>
<dd><p>Add a key-value pair</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.SortedPriorityQueue.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#SortedPriorityQueue.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.SortedPriorityQueue.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the queue is empty</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.SortedPriorityQueue.min">
<code class="sig-name descname">min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#SortedPriorityQueue.min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.SortedPriorityQueue.min" title="Permalink to this definition">¶</a></dt>
<dd><p>Return but do not remove (k, v) tuple with minimum key</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.SortedPriorityQueue.remove_min">
<code class="sig-name descname">remove_min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#SortedPriorityQueue.remove_min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.SortedPriorityQueue.remove_min" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return (k, v) tuple with minimum key</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.PriorityQueue.UnsortedPriorityQueue">
<em class="property">class </em><code class="sig-prename descclassname">toydata.PriorityQueue.</code><code class="sig-name descname">UnsortedPriorityQueue</code><a class="reference internal" href="_modules/toydata/PriorityQueue.html#UnsortedPriorityQueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.UnsortedPriorityQueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.PriorityQueue.PriorityQueueBase" title="toydata.PriorityQueue.PriorityQueueBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.PriorityQueue.PriorityQueueBase</span></code></a></p>
<p>A min-oriented priority queue implemented with an unsorted list</p>
<dl class="method">
<dt id="toydata.PriorityQueue.UnsortedPriorityQueue.add">
<code class="sig-name descname">add</code><span class="sig-paren">(</span><em class="sig-param">key</em>, <em class="sig-param">val</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#UnsortedPriorityQueue.add"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.UnsortedPriorityQueue.add" title="Permalink to this definition">¶</a></dt>
<dd><p>Add a key-val pair</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.UnsortedPriorityQueue.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#UnsortedPriorityQueue.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.UnsortedPriorityQueue.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the queue is empty</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.UnsortedPriorityQueue.min">
<code class="sig-name descname">min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#UnsortedPriorityQueue.min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.UnsortedPriorityQueue.min" title="Permalink to this definition">¶</a></dt>
<dd><p>Return but do not remove (k, v) tuple with minimum key</p>
</dd></dl>

<dl class="method">
<dt id="toydata.PriorityQueue.UnsortedPriorityQueue.remove_min">
<code class="sig-name descname">remove_min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/PriorityQueue.html#UnsortedPriorityQueue.remove_min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.PriorityQueue.UnsortedPriorityQueue.remove_min" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return (k. v) tuple with minimum key</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.Queue">
<span id="toydata-queue-module"></span><h2>toydata.Queue module<a class="headerlink" href="#module-toydata.Queue" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.Queue.ArrayDeque">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Queue.</code><code class="sig-name descname">ArrayDeque</code><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Queue.ArrayQueue" title="toydata.Queue.ArrayQueue"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Queue.ArrayQueue</span></code></a></p>
<p>Double-Ended Queues implementation using Python list
as unedrlying storage.</p>
<p>[Michael T. Goodrich]The efficiency of an ArrayDeque is similar to
that of an ArrayQueue, with all operations having O(1) running time,
but with that bound being     amortized for operations that may change
the size if the underlying list.</p>
<dl class="method">
<dt id="toydata.Queue.ArrayDeque.add_first">
<code class="sig-name descname">add_first</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.add_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.add_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Add element to the front of deque.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayDeque.add_last">
<code class="sig-name descname">add_last</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.add_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.add_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Add element to the bacl of deque</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayDeque.delete_first">
<code class="sig-name descname">delete_first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.delete_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.delete_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the first element from deque.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayDeque.delete_last">
<code class="sig-name descname">delete_last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.delete_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.delete_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the last element from deque.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayDeque.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the first element of deque;
an error occurs if the deque is emppty.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayDeque.last">
<code class="sig-name descname">last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayDeque.last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayDeque.last" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the last element of deque.</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Queue.ArrayQueue">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Queue.</code><code class="sig-name descname">ArrayQueue</code><a class="reference internal" href="_modules/toydata/Queue.html#ArrayQueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayQueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>FIFO queue implementation using Python list
as unedrlying storage.</p>
<dl class="attribute">
<dt id="toydata.Queue.ArrayQueue.DEFAULT_CAPACITY">
<code class="sig-name descname">DEFAULT_CAPACITY</code><em class="property"> = 10</em><a class="headerlink" href="#toydata.Queue.ArrayQueue.DEFAULT_CAPACITY" title="Permalink to this definition">¶</a></dt>
<dd></dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayQueue.dequeue">
<code class="sig-name descname">dequeue</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayQueue.dequeue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayQueue.dequeue" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the first element.
Raise Empty error if queue is empty</p>
<p>Time complexity: O(1)*</p>
<p>Note that <cite>*</cite> means amortized.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayQueue.enqueue">
<code class="sig-name descname">enqueue</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayQueue.enqueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayQueue.enqueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Add an element to the back of the queue</p>
<p>Time complexity: O(1)*</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayQueue.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayQueue.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayQueue.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the first element.
Raise Empty Error if the queue is empty</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.ArrayQueue.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#ArrayQueue.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.ArrayQueue.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the queue is empty</p>
<p>Time complexity: O(1)</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Queue.LinkedDeque">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Queue.</code><code class="sig-name descname">LinkedDeque</code><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Queue._DoublyLinkedBase</span></code></p>
<p>Double-ended queue implementation based on a doubly linked list</p>
<p>All the operation with time complexity O(1)</p>
<dl class="method">
<dt id="toydata.Queue.LinkedDeque.delete_first">
<code class="sig-name descname">delete_first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.delete_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.delete_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the element from the front of the deque
Raise Empty exception if the deque is empty.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedDeque.delete_last">
<code class="sig-name descname">delete_last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.delete_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.delete_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the element from the back of the deque
Raise Empty exception if the deque is empty.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedDeque.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return(but not remove) the element at the front of the queue</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedDeque.insert_first">
<code class="sig-name descname">insert_first</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.insert_first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.insert_first" title="Permalink to this definition">¶</a></dt>
<dd><p>Add an element to the front of the deque</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedDeque.insert_last">
<code class="sig-name descname">insert_last</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.insert_last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.insert_last" title="Permalink to this definition">¶</a></dt>
<dd><p>Add an element to the back if the deque</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedDeque.last">
<code class="sig-name descname">last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedDeque.last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedDeque.last" title="Permalink to this definition">¶</a></dt>
<dd><p>Return(but not remove) the element at the back of the deque</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Queue.LinkedQueue">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Queue.</code><code class="sig-name descname">LinkedQueue</code><a class="reference internal" href="_modules/toydata/Queue.html#LinkedQueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedQueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.LinkedLists.Singlellist" title="toydata.LinkedLists.Singlellist"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.LinkedLists.Singlellist</span></code></a></p>
<p>FIFO queue implementation using a single linked list for storage</p>
<dl class="method">
<dt id="toydata.Queue.LinkedQueue.dequeue">
<code class="sig-name descname">dequeue</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedQueue.dequeue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedQueue.dequeue" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the first element if the queue(i.e., FIFO).</p>
<p>Raisee Empty exception if the dueue is empty</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedQueue.enqueue">
<code class="sig-name descname">enqueue</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedQueue.enqueue"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedQueue.enqueue" title="Permalink to this definition">¶</a></dt>
<dd><p>Add an element to the back of the queue</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedQueue.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedQueue.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedQueue.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return(but do not remove) the element at the front if the queue</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Queue.LinkedQueue.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Queue.html#LinkedQueue.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Queue.LinkedQueue.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the queue is empty</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.SearchTree">
<span id="toydata-searchtree-module"></span><h2>toydata.SearchTree module<a class="headerlink" href="#module-toydata.SearchTree" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.SearchTree.AVLTreeMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.SearchTree.</code><code class="sig-name descname">AVLTreeMap</code><span class="sig-paren">(</span><em class="sig-param">root=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#AVLTreeMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.AVLTreeMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.SearchTree.TreeMap" title="toydata.SearchTree.TreeMap"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.SearchTree.TreeMap</span></code></a></p>
<p>Sorted map implementation using an AVL tree.</p>
<p>Space complexity: O(n)
Time complexity(Worst): 
find_range: O(s + logn)
others: O(logn)
iter, reversed: O(n)
in other word: AVL Tree can ensure h = logn</p>
</dd></dl>

<dl class="class">
<dt id="toydata.SearchTree.RedBlackTreeMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.SearchTree.</code><code class="sig-name descname">RedBlackTreeMap</code><span class="sig-paren">(</span><em class="sig-param">root=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#RedBlackTreeMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.RedBlackTreeMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.SearchTree.TreeMap" title="toydata.SearchTree.TreeMap"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.SearchTree.TreeMap</span></code></a></p>
<p>Sorted map implementation using a red-black tree</p>
</dd></dl>

<dl class="class">
<dt id="toydata.SearchTree.SplayTreeMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.SearchTree.</code><code class="sig-name descname">SplayTreeMap</code><span class="sig-paren">(</span><em class="sig-param">root=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#SplayTreeMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.SplayTreeMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.SearchTree.TreeMap" title="toydata.SearchTree.TreeMap"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.SearchTree.TreeMap</span></code></a></p>
<p>Sorted map implementation using a splay tree</p>
</dd></dl>

<dl class="class">
<dt id="toydata.SearchTree.TreeMap">
<em class="property">class </em><code class="sig-prename descclassname">toydata.SearchTree.</code><code class="sig-name descname">TreeMap</code><span class="sig-paren">(</span><em class="sig-param">root=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Tree.LinkedBinaryTree" title="toydata.Tree.LinkedBinaryTree"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Tree.LinkedBinaryTree</span></code></a>, <a class="reference internal" href="#toydata.Maps.MapBase" title="toydata.Maps.MapBase"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Maps.MapBase</span></code></a></p>
<p>Base class, Sorted map implementation using a binary search tree.</p>
<p>Space complexity: O(n)
Time complexity(Worst): 
find_range: O(s + h)
iter, reversed: O(n)
others: O(h)
h = the height of the tree(n when worst)</p>
<dl class="class">
<dt id="toydata.SearchTree.TreeMap.Position">
<em class="property">class </em><code class="sig-name descname">Position</code><span class="sig-paren">(</span><em class="sig-param">container</em>, <em class="sig-param">node</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.Position"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.Position" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Tree.Position</span></code></p>
<dl class="method">
<dt id="toydata.SearchTree.TreeMap.Position.key">
<code class="sig-name descname">key</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.Position.key"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.Position.key" title="Permalink to this definition">¶</a></dt>
<dd><p>Return key of maps’s key-value pair</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.Position.value">
<code class="sig-name descname">value</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.Position.value"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.Position.value" title="Permalink to this definition">¶</a></dt>
<dd><p>Return value of map’s key-value pair</p>
</dd></dl>

</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.after">
<code class="sig-name descname">after</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.after"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.after" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position just after p in the natural order.
Return None if p is the last position</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.before">
<code class="sig-name descname">before</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.before"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.before" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position just before p in the natural order.
Return None if p is the first position.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.delete">
<code class="sig-name descname">delete</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.delete"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.delete" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove the item at given Position</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.find_ge">
<code class="sig-name descname">find_ge</code><span class="sig-paren">(</span><em class="sig-param">k</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.find_ge"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.find_ge" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with least key greater than
or equal to k. Return None if there does not exist such a key.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.find_min">
<code class="sig-name descname">find_min</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.find_min"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.find_min" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (key, value) pair with minimum key(or None if empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.find_position">
<code class="sig-name descname">find_position</code><span class="sig-paren">(</span><em class="sig-param">k</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.find_position"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.find_position" title="Permalink to this definition">¶</a></dt>
<dd><p>Return position with key k, or else neighbor(or None if empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.find_range">
<code class="sig-name descname">find_range</code><span class="sig-paren">(</span><em class="sig-param">start</em>, <em class="sig-param">stop</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.find_range"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.find_range" title="Permalink to this definition">¶</a></dt>
<dd><p>Iterate all (key, value) pairs such that
start &lt;= key &lt; stop.</p>
<p>If start is None, iteration begins with minimum key of map..
If stop is None, iteration continues throungh the maximum key
of map</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.first">
<code class="sig-name descname">first</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.first"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.first" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the first Position in the tree(or None if empty)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.SearchTree.TreeMap.last">
<code class="sig-name descname">last</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/SearchTree.html#TreeMap.last"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.SearchTree.TreeMap.last" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the last Position in the etree(or None if empty)</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.Stack">
<span id="toydata-stack-module"></span><h2>toydata.Stack module<a class="headerlink" href="#module-toydata.Stack" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.Stack.ArrayStack">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Stack.</code><code class="sig-name descname">ArrayStack</code><a class="reference internal" href="_modules/toydata/Stack.html#ArrayStack"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.ArrayStack" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>LIFO Srtack implementation using Python list as underlyinh storage.</p>
<dl class="method">
<dt id="toydata.Stack.ArrayStack.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#ArrayStack.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.ArrayStack.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the stack is empty
Time Complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.ArrayStack.pop">
<code class="sig-name descname">pop</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#ArrayStack.pop"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.ArrayStack.pop" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the element from the top of the stack(LIFO)
Raise Empty exception if the stack is empty.
Time Complexity: O(1)*</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.ArrayStack.push">
<code class="sig-name descname">push</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#ArrayStack.push"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.ArrayStack.push" title="Permalink to this definition">¶</a></dt>
<dd><p>Add element to the top of the stack
Time Complexity: O(1)*
Note: “*” in here means amortization</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.ArrayStack.top">
<code class="sig-name descname">top</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#ArrayStack.top"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.ArrayStack.top" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (but not remove) at the top of the stack.
Raise Empty exception if the stack in empty.
Time Complexity: O(1)</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Stack.LinkedStack">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Stack.</code><code class="sig-name descname">LinkedStack</code><a class="reference internal" href="_modules/toydata/Stack.html#LinkedStack"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.LinkedStack" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.LinkedLists.Singlellist" title="toydata.LinkedLists.Singlellist"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.LinkedLists.Singlellist</span></code></a></p>
<p>LIFO Srtack implementation using Python list as underlyinh storage.</p>
<dl class="method">
<dt id="toydata.Stack.LinkedStack.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#LinkedStack.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.LinkedStack.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the stack is empty
Time Complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.LinkedStack.pop">
<code class="sig-name descname">pop</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#LinkedStack.pop"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.LinkedStack.pop" title="Permalink to this definition">¶</a></dt>
<dd><p>Remove and return the element from the top of the stack(LIFO)
Raise Empty exception if the stack is empty.
Time Complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.LinkedStack.push">
<code class="sig-name descname">push</code><span class="sig-paren">(</span><em class="sig-param">e</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#LinkedStack.push"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.LinkedStack.push" title="Permalink to this definition">¶</a></dt>
<dd><p>Add element to the top of the stack
Time Complexity: O(1)
Note: “*” in here means amortization</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Stack.LinkedStack.top">
<code class="sig-name descname">top</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Stack.html#LinkedStack.top"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Stack.LinkedStack.top" title="Permalink to this definition">¶</a></dt>
<dd><p>Return (but not remove) at the top of the stack.
Raise Empty exception if the stack in empty.
Time Complexity: O(1)</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.Tree">
<span id="toydata-tree-module"></span><h2>toydata.Tree module<a class="headerlink" href="#module-toydata.Tree" title="Permalink to this headline">¶</a></h2>
<dl class="class">
<dt id="toydata.Tree.BinaryTree">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Tree.</code><code class="sig-name descname">BinaryTree</code><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Tree.Tree" title="toydata.Tree.Tree"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Tree.Tree</span></code></a></p>
<p>Abstract base class representing a binary tree structure</p>
<dl class="method">
<dt id="toydata.Tree.BinaryTree.children">
<code class="sig-name descname">children</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.children"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.children" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate an iteration of Positions representing p’s children</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.BinaryTree.inorder">
<code class="sig-name descname">inorder</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.inorder"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.inorder" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate an inorder iteration of positions in the tree</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.BinaryTree.left">
<code class="sig-name descname">left</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.left"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.left" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a Position representing p’s left child</p>
<p>Return None if p does not have a left child</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.BinaryTree.positions">
<code class="sig-name descname">positions</code><span class="sig-paren">(</span><em class="sig-param">trav_method='preorder'</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.positions"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.positions" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate an iteration of the tree’s positions</p>
<p>Methods: preorder, postorder, breadthfirst, inorder</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.BinaryTree.right">
<code class="sig-name descname">right</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.right"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.right" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a Position representing p’s right child</p>
<p>Return None if p does not have a right child</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.BinaryTree.sibling">
<code class="sig-name descname">sibling</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#BinaryTree.sibling"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.BinaryTree.sibling" title="Permalink to this definition">¶</a></dt>
<dd><p>Return a Position representing p’s sibling(or None if no sibling)</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Tree.LinkedBinaryTree">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Tree.</code><code class="sig-name descname">LinkedBinaryTree</code><span class="sig-paren">(</span><em class="sig-param">root=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <a class="reference internal" href="#toydata.Tree.BinaryTree" title="toydata.Tree.BinaryTree"><code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Tree.BinaryTree</span></code></a></p>
<p>Linked representation of a binary tree structure</p>
<dl class="class">
<dt id="toydata.Tree.LinkedBinaryTree.Position">
<em class="property">class </em><code class="sig-name descname">Position</code><span class="sig-paren">(</span><em class="sig-param">container</em>, <em class="sig-param">node</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.Position"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.Position" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">toydata.Tree.Position</span></code></p>
<p>An abstraction representing the location of a single element</p>
<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.Position.element">
<code class="sig-name descname">element</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.Position.element"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.Position.element" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the element at this Position</p>
</dd></dl>

</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.left">
<code class="sig-name descname">left</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.left"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.left" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position of p’s left child(or None if no left child)</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.num_children">
<code class="sig-name descname">num_children</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.num_children"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.num_children" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the number of children of Position p</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.parent">
<code class="sig-name descname">parent</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.parent"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.parent" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position of p’s parent(or None if p is root)</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.preorder_indent">
<em class="property">static </em><code class="sig-name descname">preorder_indent</code><span class="sig-paren">(</span><em class="sig-param">T</em>, <em class="sig-param">p</em>, <em class="sig-param">d</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.preorder_indent"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.preorder_indent" title="Permalink to this definition">¶</a></dt>
<dd><p>Print preorder representation of subtree of T rooted at p
at depth d.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.right">
<code class="sig-name descname">right</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.right"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.right" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the Position of p’s right child(or None if no right child)</p>
<p>Time complexity: O(1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.LinkedBinaryTree.root">
<code class="sig-name descname">root</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#LinkedBinaryTree.root"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.LinkedBinaryTree.root" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the root Position of the tree(or None if tree is empty)</p>
<p>Time complexity: O(1)</p>
</dd></dl>

</dd></dl>

<dl class="class">
<dt id="toydata.Tree.Tree">
<em class="property">class </em><code class="sig-prename descclassname">toydata.Tree.</code><code class="sig-name descname">Tree</code><a class="reference internal" href="_modules/toydata/Tree.html#Tree"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>Abstract base class representing a tree structure.</p>
<dl class="class">
<dt id="toydata.Tree.Tree.Position">
<em class="property">class </em><code class="sig-name descname">Position</code><a class="reference internal" href="_modules/toydata/Tree.html#Tree.Position"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.Position" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">object</span></code></p>
<p>An abstraction representation the location of a single element.</p>
<dl class="method">
<dt id="toydata.Tree.Tree.Position.element">
<em class="property">abstract </em><code class="sig-name descname">element</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.Position.element"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.Position.element" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the element store at this Position</p>
</dd></dl>

</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.breadthfirst">
<code class="sig-name descname">breadthfirst</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.breadthfirst"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.breadthfirst" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate a breath-first iteration of the positions of the tree</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.children">
<em class="property">abstract </em><code class="sig-name descname">children</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span> &#x2192; Iterator<a class="reference internal" href="_modules/toydata/Tree.html#Tree.children"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.children" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate an iteration of Positions representing p’s children</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.depth">
<code class="sig-name descname">depth</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.depth"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.depth" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the number of levels separating Position p from the root</p>
<p>Top -&gt; Bottom</p>
<p>Time complexity: O(d_p + 1)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.height">
<code class="sig-name descname">height</code><span class="sig-paren">(</span><em class="sig-param">p=None</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.height"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.height" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the height of the subtree rooted at Position P.</p>
<p>If p is None ,return the height of the entire tree</p>
<p>Time complexity: O(n)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.is_empty">
<code class="sig-name descname">is_empty</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.is_empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.is_empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if the tree is empty</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.is_leaf">
<code class="sig-name descname">is_leaf</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.is_leaf"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.is_leaf" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if Position p does not have any children</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.is_root">
<code class="sig-name descname">is_root</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.is_root"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.is_root" title="Permalink to this definition">¶</a></dt>
<dd><p>Return True if Position p represent the root of the tree</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.num_children">
<em class="property">abstract </em><code class="sig-name descname">num_children</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.num_children"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.num_children" title="Permalink to this definition">¶</a></dt>
<dd><p>Return the number of children that Position p has</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.parent">
<em class="property">abstract </em><code class="sig-name descname">parent</code><span class="sig-paren">(</span><em class="sig-param">p</em><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.parent"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.parent" title="Permalink to this definition">¶</a></dt>
<dd><p>Return Position representing p’s parent(or None if p is root)</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.postorder">
<code class="sig-name descname">postorder</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.postorder"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.postorder" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate a postorder iteration of positions in the tree.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.preorder">
<code class="sig-name descname">preorder</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.preorder"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.preorder" title="Permalink to this definition">¶</a></dt>
<dd><p>Generate a preorder iteration of positions in the tree.</p>
</dd></dl>

<dl class="method">
<dt id="toydata.Tree.Tree.root">
<em class="property">abstract </em><code class="sig-name descname">root</code><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="reference internal" href="_modules/toydata/Tree.html#Tree.root"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.Tree.Tree.root" title="Permalink to this definition">¶</a></dt>
<dd><p>Return Position representing the tree’s root(or None if empty)</p>
</dd></dl>

</dd></dl>

</div>
<div class="section" id="module-toydata.utils">
<span id="toydata-utils-module"></span><h2>toydata.utils module<a class="headerlink" href="#module-toydata.utils" title="Permalink to this headline">¶</a></h2>
<dl class="exception">
<dt id="toydata.utils.Empty">
<em class="property">exception </em><code class="sig-prename descclassname">toydata.utils.</code><code class="sig-name descname">Empty</code><a class="reference internal" href="_modules/toydata/utils.html#Empty"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#toydata.utils.Empty" title="Permalink to this definition">¶</a></dt>
<dd><p>Bases: <code class="xref py py-class docutils literal notranslate"><span class="pre">Exception</span></code></p>
</dd></dl>

</div>
<div class="section" id="module-toydata">
<span id="module-contents"></span><h2>Module contents<a class="headerlink" href="#module-toydata" title="Permalink to this headline">¶</a></h2>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
      
        <a href="modules.html" class="btn btn-neutral float-left" title="toydata" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2019, Xiangzhuang Shen

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
   

</body>
</html>